The present invention relates to the scheduling of transmissions without collisions in ad hoc networks in which routers can move and have both hosts and networks attached to them.
Many medium-access control (MAC) protocols have been developed for wireless networks. The carrier-sense multiple access (CSMA) protocol was the first to be used in multihop packet-radio networks. A limitation of CSMA in multihop networks is that sources hidden from one another cannot detect their transmissions, which degrades CSMA""s performance to that of the pure ALOHA protocol. Many MAC protocols have been proposed and implemented to solve the hidden-terminal problems of CSMA. The throughput of CSMA protocols is very good, as long as the multiple transmitters within range of the same receivers can sense one another""s transmissions. Unfortunately, xe2x80x9chidden terminalxe2x80x9d problems degrade the performance of CSMA substantially, because carrier sensing cannot prevent collisions in that case.
The busy tone multiple access (BTMA) protocol (F. A. Tobagi and L. Kleinrock, xe2x80x9cPacket switching in radio channels: Part IIxe2x80x94the hidden terminal problem in carrier sense multiple-access modes and the busy-tone solution,xe2x80x9d IEEE Trans. Commun., vol. COM-23, no. 12, pp. 1417-1433, 1975.) was the first proposal to combat the hidden-terminal problems of CSMA. BTMA is designed for station-based networks and divides the channel into a message channel and the busy-tone channel. The base station transmits a busy-tone signal on the busy-tone channel as long as it senses carrier on the data channel. Because the base station is in line of sight of all terminals, each terminal can sense the busy-tone channel to determine the state of the data channel. The limitations of BTMA are the use of a separate channel to convey the state of the data channel, the need for the receiver to transmit the busy tone while detecting carrier in the data channel, and the difficulty of detecting the busy-tone signal in a narrow-band channel.
A receiver initiated busy-tone multiple access protocol for packet-radio networks has also been proposed (C. Wu and V. O. K. Li, xe2x80x9cReceiver-initiated busy-tone multiple access in packet radio networks,xe2x80x9d ACM SIGCOMM 87 Workshop: Frontiers in Computer Communications Technology, Stowe, Vt., USA, 11-13 August 1987). In this scheme, the sender transmits a request-to-send (RTS) to the receiver, before sending a data packet. When the receiver obtains a correct RTS, it transmits a busy tone in a separate channel to alert other sources that they should back off. The correct source is always notified that it can proceed with transmission of the data packet. The limitations of this scheme are that it still requires a separate busy-tone channel and full-duplex operation at the receiver.
Several protocols have been proposed based on different types of xe2x80x9ccollision-avoidance xe2x80x9d handshakes done with small control packets and meant to avoid data collisions when sources of data packets cannot hear one another. The collision-avoidance approach in the prior art follows the basic philosophy first introduced by Tobagi and Kleinrock in the Split-Channel Reservation Multiple Access (SRMA) protocol (F. A. Tobagi and L. Kleinrock, xe2x80x9cPacket switching in radio channels: Part IIIxe2x80x94polling and (dynamic) split-channel reservation multiple access,xe2x80x9d IEEE Trans. Commun., vol. COM-24, no. 8, pp. 832-845, 1976). In SRMA, and most subsequent collision-avoidance protocols, a sender node sends a request-to-send (RTS) packet to the intended receiver, either sensing the channel before sending the RTS or not sensing the channel before the RTS transmission. A receiver that hears a clean RTS responds with a clear-to-send (CTS), and the sender can send a data packet after hearing a clean CTS.
U.S. Pat. No. 5,319,641 assigned to Echelon Systems Corp. discloses a method to improve CSMA p-persistent protocols by introducing a random waiting time that stations must wait listening to the channel once they have packets to send. The method disclosed does not work in networks with hidden terminals.
U.S. Pat. No. 4,661,902 assigned to Apple Computer, Inc. discloses a method that amounts to an implementation of SRMA over a single channel in which stations use carrier sensing before sending RTSs.
MACA (P. Karn, xe2x80x9cMACHxe2x80x94a new channel access method for packet radio,xe2x80x9d in ARRL/CRRL Amateur Radio 9th Computer Networking Conference, pp. 134-40, ARRL, 1990) includes a technique that amounts to SRMA running over a single channel in which a request-to-send (RTS) packet is sent without carrier sensing. There is no description of how to support packet trains.
U.S. Pat. No. 5,231,634 assigned to Proxim, Inc. discloses a method that also applies SRMA""s basic approach over a single channel. The RTS specifies the length of the impending data packet.
U.S. Pat. No. 5,502,724 assigned to International Business Machines Corporation discloses a method that extends the collision avoidance handshake to allow for multiple data packets to flow among a pair of communicating stations. A station that intends to establish a connection with a second station senses the channel. If the channel is idle, it sends a connection request (CR) packet to the intended receiver station. The CR specifies the number of data packets that the connection includes. The intended receiver sends a connection confirm (CC) packet to the sending station; the CC also specifies the number of packet in the connection. After the exchange of correct CR and CC packets the sending station may send one or multiple data packets and the receiving station may send an acknowledgment packet specifying which data packets were received correctly. To end the connection, the sending station sends a disconnect request (DR) and the receiving station issues a disconnect confirm (DC). Stations that receive a CR packet back off for an amount of time that is long enough for the advertised number of data packets to be sent to the receiver. After receiving a CR or CC, a station can attempt to access the channel when a timer proportional to the number of packets to be sent in the connection expire, or when it receives a DR or DC packet. The limitation with the method disclosed in U.S. Pat. No. 5,502,724 is that the method cannot ensure collision-fee transmissions of data packets, even with the transmission of CC packets by the receiver. The need for feedback from the receiver to its neighbors on a packet-by-packet basis was demonstrated by Fullmer and Garcia-Luna-Aceves (C. L. Fullmer and J. J. Garcia Luna-Aceves, xe2x80x9cSolutions to Hidden Terminal Problems in Wireless Networksxe2x80x9d, Proc. ACM SIGCOMM 97, Cannes, France, Sep. 14-18, 1997). Because the CC packet sent by the receiver may collide with another packet at a neighbor of a receiver, the CC packet does not provide sufficient feedback to hidden nodes; furthermore, the need for feedback packets to be longer than request packets was also demonstrated by Fullmer and Garcia-Luna-Aceves (C. L. Fullmer and J. J. Garcia-Luna-Aceves, xe2x80x9cFloor Acquisition Multiple Access (FAMA) for Packet-Radio Networks,xe2x80x9d Proc. ACM SIGCOMM 95, Cambridge, Mass., Aug. 28-Sep. 1, 1995). In addition, even though the disclosed method makes reference to broadcast packets sent to all the neighbors of a station, it provides no provisions to ensure that broadcast or multicast packets are received without interference by all the neighbors of a sending station.
U.S. Pat. No. 5,721,725 assigned to Xerox Corp. discloses a method similar to SRMA, and describes it to be an improvement over MACH. The method disclosed extends MACH by specifying in the RTS packets the desired data rate for data packets and allowing sender and receiver to negotiate the transmission data rate. This method fails to guarantee collision free transmissions in networks with hidden terminals because no provisions are made on the length of the CTS being longer than the length of any RTS to ensure that collisions of RTSs and CTSs are detected by hidden stations.
DFWMAC IEEE802.11 (K. C. Chen, xe2x80x9cMedium Access Control of Wireless LANs for Mobile Computing,xe2x80x9d IEEE Network, vol. 8, no. 5, pp. 50-63, 1994), FAMA-NCS (C. L. Fullmer and J. J. Garcia-Luna-Aceves, xe2x80x9cSolutions to Hidden Terminal Problems in Wireless Networksxe2x80x9d, Proc. ACM SIGCOMM 97, Cannes, France, Sep. 14-18, 1997), and RIMA (J. J. Garcia-Luna-Aceves and A. Tzamaloukas, xe2x80x9cReversing the Collision Avoidance Handshake in Wireless networks,xe2x80x9d Proc. ACM/IEEE Mobicom 99, August 1999) are three recent additional examples of collision-avoidance protocols. IEEE 802.11 is a method very similar to SRMA with carrier sensing for the transmission of RTSs. The objective of FAMA-NCS is for a station that has data to send to acquire control of the channel in the vicinity of the receiver (which we call xe2x80x9cthe floorxe2x80x9d) before sending any data packet, and to ensure that no data packet collides with any other packet at the receiver. FAMA-NCS makes the length of CTSs much longer than the length of RTSs in order to detect the collision of RTSs with CTSs, which cannot be enforced in prior collision-avoidance protocols. RIMA includes a family of protocols that reverse the collision-avoidance handshake method first introduced in SRMA and makes the receiver polls the sender of data. Several other medium access control (MAC) protocols have been proposed for either single-channel wireless networks or wireline local area networks that are based on similar RTS-CTS exchanges, or based on RTSs followed by pauses. However, despite the popularity gained by collision-avoidance protocols and systems based on such protocols over the past few years, two key performance limitations of all collision-avoidance MAC protocols are that: (a) they cannot provide channel-access delay guarantees, which represents a big problem for real-time applications; and (b) they lack explicit support of collision-free multicasting or broadcasting, which implies that either a node must transmit the same multicast packet multiple times, once to each multicast-group neighbor, or packets are sent with likelihood of reception as low as the ALOHA protocol. In addition, collision-avoidance protocols require carrier sensing, which is not technically or economically feasible to implement correctly in direct sequence spread spectrum radios with very high chip rates.
To circumvent hidden-terminal interference problems, unique codes (spreading codes or frequency-hopping sequences) can be assigned to receivers or senders.
An example of this approach was the Metricom network. However, receiver oriented code assignment (ROCA) and transmitter oriented code assignment (TOCA) require either pre-configuring radios with the node to code mappings, or finding the codes being used by neighboring transmitters or receivers. Furthermore, efficient broadcasting is not guaranteed simply by establishing a TOCA approach; because all the neighbors of a transmitter must agree to listen to the transmitter at the same time to minimize the number of transmissions.
Another approach to channel access used in multihop wireless networks includes establishing transmission schedules, i.e., allocating stations to different times and data channels (e.g., frequencies, spreading codes, or their combination) in a way that no collisions occur. Transmission scheduling can be static or dynamic; MAC protocols based on dynamic transmission scheduling explore the spatial reuse of the radio channel and thus have much higher channel utilization than such fixed scheduling approaches as TDMA and FDMA.
In TDMA protocols, time is divided into frames comprising time slots. Time slots are allocated to specific nodes or a centralized station is used to allocate the time slots. The limitations of TDMA stem from the fixed assignment of time slots to nodes, which are slow to adapt to network changes and makes inefficient use of the channel if nodes are bursty sources of traffic, and the use of centralized assignments.
There are many approaches in the prior art based on dynamic TDMA methods in which stations use ALOHA, slotted ALOHA or other contention protocols in an uplink to request time slots from a base station. An example of this approach is the system disclosed in U.S. Pat. No. 5,638,371 assigned to NEC USA, Inc. The present invention eliminates the need for a base station to make slot assignments.
A number of protocols have been proposed in the recent past to provide dynamic time-slot allocation without requiring central base stations. These protocols can be classified as topology-independent and topology-dependent time scheduling protocols.
Shepard (T. Shepard, xe2x80x9cA Channel Access Scheme for Large Dense Packet Radio Networks,xe2x80x9d Proc. SIGCOMM ""96, 1996; T. Shepard, xe2x80x9cScalable, Self-Configuring Packet Radio Network Having Decentralized Channel Management Providing Collision-Free Packet Transfer,xe2x80x9d U.S. Pat. No. 5,682,382, Oct. 28, 1997), Chlamtac et al (I. Chlamtac et al, xe2x80x9cTime-Spread Multiple-Access (TSMA) Protocols for Multihop Mobile Radio Networks,xe2x80x9d IEEE/ACM Transactions on Networking, ""Vol. 5, no. 6, December 1997), and Ju and Li (Ji-Her Ju, Victor O. K. Li, xe2x80x9cAn Optimal Topology-Transparent Scheduling Method in Multihop Packet Radio Networks,xe2x80x9d IEEE/ACM Transactions on Networking, Vol. 6, no. 3, June 1998) have proposed topology-independent time-scheduling protocols. In these protocols, nodes are pre-assigned (by means of their nodal IDs, for example) or adopt a transmission schedule that they publish, and such a schedule specifies the times when a node transmits and receives. The protocols guarantee or provide a high likelihood that at least one transmission time in a node""s schedule does not conflict with any node one or two hops away. In the Chlamtac and Ju approaches, nodes are unable to determine which transmissions will succeed, complicating the job of higher layer (e.g., link-layer) protocols. These approaches also require values for the total number of nodes in the network and maximum number of neighbors for each node, as input parameters to the algorithm, thus making them design for the worst case conditions (and thus, inefficient if the network is not as dense as expected), or being sensitive to actual network conditions (if the network is larger or more dense than expected). Shepard""s approach avoids collisions by assuming nodes are synchronized with their neighbors, have knowledge of their neighbors"" schedules, and are able to receive from multiple transmitting neighbors simultaneously. This final assumption requires fairly sophisticated radio hardware.
Zhu and Corson (C. Zhu, M. S. Corson, xe2x80x9cA Five-Phase Reservation Protocol (FPRP) for Mobile Ad Hoc Networks,xe2x80x9d Proc. IEEE INFOCOM ""98) and Tang and Garcia-Luna Aceves (Z. Tang and J. J. Garcia-Luna-Aceves, xe2x80x9cA Protocol for Topology-Dependent Transmission Scheduling,xe2x80x9d Proc. IEEE Wireless Communications and Networking Conference 1999 (WCNC 99), New Orleans, La., Sep. 21-24, 1999; Z. Tang and J. J. Garcia-Luna-Aceves, xe2x80x9cHop-Reservation Multiple Access (HRMA) for Multichannel Packet Radio Networksxe2x80x9d, Proc. IEEE IC3N ""98: Seventh International Conference on Computer Communications and Networks, Lafayette, La., Oct. 12-15, 1998) have developed topology-dependent scheduling protocols, such that a node acquires a transmission schedule that allows the node to transmit without interfering with nodes one and two hops away from itself, and such that channel reuse is increased as the number of neighbors per node decreases. These protocols require nodes to contend in order to reserve collision-free time slots, and the contention is done on each mini-slot. Furthermore, they rely on dividing each slot into several mini-slots. All this limits the minimum duration that slots may have. The present invention does not require slots to be subdivided, and does not require nodes to reply to neighbors in less than a frame time.
Several approaches have been proposed that are based on TDMA and require an initial, topology-independent schedule, followed by communication among the network nodes to negotiate a final schedule. Chlamtac (I. Chlamtac, xe2x80x9cFair Algorithms for Maximal Link Activation in Multihop Radio Networks,xe2x80x9d IEEE Transactions on Communications, Vol. COM-35, no. 7, July, 1987) proposed an algorithm based on a repeating link schedule that can adapt to traffic demands after some number of iterations of the algorithm. The algorithm starts with a xe2x80x9csingle-slot-per-linkxe2x80x9d schedule, such as provided by assigning each node a transmission slot according to its node ID. At each iteration, schedule information and a scheduling xe2x80x9ctokenxe2x80x9d are routed up and down a routing tree (established by means of pre-existing algorithms), to assign additional slots to nodes or links according to their degree of unmet traffic demands. Ephremides and Truong (A. Ephremides, T. Truong, xe2x80x9cScheduling Broadcasts in Multihop Radio Networks,xe2x80x9d IEEE Transactions on Communications, Vol. COM-38, No. 4, April, 1990) proposed a similar algorithm in which each node is initially assigned a slot corresponding to its node ID, and then each node uses their assignment to pass xe2x80x9cskeletonxe2x80x9d schedules to their neighbors. During the next two frames (two iterations of communicating schedules), and in accordance with fixed node priorities, nodes are able to grab available slots until all available slots are taken (i.e., no more slots can be assigned without causing collisions). Because of the need for schedules that are fixed, requiring a few iterations to converge, and of scheduling-frame size equal to the maximum size of the network, these approaches have limited scalability and robustness to mobility or other dynamics. The approach proposed by Young (C. D. Young, xe2x80x9cUSAP: A Unifying Dynamic Distributed Multichannel TDMA Slot Assignment Protocol,xe2x80x9d Proc. IEEE MILCOM 96 OCTOBER 1996) also requires initial assignment of one slot per node, and then negotiation of scheduling packets for assignment of the other slots. However, the initially assigned slot is limited to the first slot in each xe2x80x9cframe.xe2x80x9d Thus, each node""s assigned slot occurs every N frames, where N is the maximum network size. Because of this, the approach does not scale. Also, the approach is relatively slow in adapting to dynamic traffic conditions, because a node needs to wait up to N frames before a proposed schedule addition is confirmed by a neighbor.
The majority of the limitations described above for the MAC protocols in the prior art are eliminated with the Robust Environmentally Adaptive Link/MAC (REALM) protocol (D. Beyer, J. J. Garcia-Luna-Aceves, and C. Fullmer, xe2x80x9cAdpative Communication Protocol for Wireless Networks,xe2x80x9d U.S. patent application Ser. No. 09/248,738, Feb. 10, 1999, in combination with the Neighborhood Established Transmission Scheduling (NETS) protocol (J. J. Garcia-Luna-Aceves, D. Beyer and C. Fullmer, xe2x80x9cA Protocol for Neighborhood Established Transmission Scheduling,xe2x80x9d Ser. No. 09/418,899, Oct. 15, 1999).
REALM is a MAC protocol that achieves collision avoidance without the need for handshakes between senders and receivers. REALM assumes a synchronous network organized into time frames divided into slots. The amount of synchronization assumed in REALM is the same type of synchronization required in any network operating with frequency hopping radios, such as those designed to operate in ISM bands and commercially available today. A node running REALM must know the identities of its one-hop and two-hop neighbors and the present time in the network (e.g., the number of the current frame). Based on this information, and auxiliary information, each node evaluates a function (e.g., a hash function) that specifies deterministically which node should transmit in which time slot of a frame. REALM achieves fairness by changing in each frame the priority with which a given node can transmit in a time slot of the frame. Once all the nodes in the two-hop neighborhood of a node have consistent information regarding their neighborhood, collisions are avoided because all the nodes use the same deterministic algorithm to select a winner for a given time slot.
Bao and Garcia-Luna-Aceves (L. Bao and J. J. Garcia-Luna-Aceves, xe2x80x9cA New Approach to Channel Access Scheduling for Ad Hoc Networks,xe2x80x9d Proc. ACM MobiCom 2001xe2x80x94Seventh Annual International Conference on Mobile Computing and networking, Jul. 16-21, 2001, Rome, Italy; L. Bao and J. J. Garcia-Luna-Aceves, xe2x80x9cChannel Access Scheduling in Ad Hoc Networks with Unidirectional Links,xe2x80x9d Proc. ACM DialM 2001xe2x80x94Fifth International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, Jul. 21, 2001 Rome, Italy; L. Bao and J. J. GarciaLuna-Aceves, xe2x80x9cA New Collision-Free Medium Access Control Protocol xe2x80x9d Proc. IEEE MILCOM 2000, Los Angeles, Calif., Oct. 22-25, 2000.) have proposed channel access algorithms that achieve collision avoidance without the need for a specific handshake between sender and receiver in a way similar to REALM. These algorithms require each node to have the identifiers of all the nodes within two hops, and assign a transmission priority to a node during a given time slot based on this neighbor information. An unspecified algorithm is assumed to disseminate neighbor information.
A limitation of using REALM by itself or the algorithms proposed by Bao and Garcia-Luna-Aceves is that these approaches are based on all the nodes in a twohop neighborhood competing for transmission in each time slot of a frame designated for such type of collision-free access. A more efficient use of he channel can be achieved if those nodes that were able to transmit during a prior frame notify their neighborhoods that they will not be competing for transmission slots for a period of time, which effectively reduces competition among nodes and the delay experienced by a given node in accessing the channel.
The present invention is directed at addressing the above-mentioned shortcomings, disadvantages and problems, and will be understood by reading and studying the following specification.
The present invention includes a medium access control (MAC) protocol for the collision-free transmission of packets into a channel, such that nodes are assigned time slots for collision-free transmission based on information they acquire regarding the constituency of their local neighborhoods and the advertisements of the time slots when nodes in local neighborhoods will attempt to transmit again.
According to one aspect of the invention, the scheduling procedure may utilize an age of the network together with unique identifiers associated with the nodes.
According to another aspect of the invention, the candidate transmission times for each node are determined using a list of the subsequent transmission times advertised by other nodes. The node discards the advertised transmission times from the list of potential transmission times, and computes its candidate transmission times using a function that provides a varying (pseudorandom) distribution of outputs for a varying sample of inputs. This function may be a hash function, an encryption function, or a table-lookup function. The computation of candidate transmission times uses the identifiers of those nodes for which no advertised transmission time has been obtained.